// https://leetcode-cn.com/problems/number-of-islands/
// 200. Number of Islands
// Given an `m x n` 2D binary grid `grid` which represents a map of '1's (land)
// and '0's (water), return the number of islands
// An island is surrounded by water and is formed by connecting adjacent lands
// horizontally or vertically. You may assume all four edges of the grid are all
// surrounded by water
function numIslands(grid: string[][]): number {
    if (grid === null || grid.length === 0) return 0;

    const m = grid.length;
    const n = grid[0].length;
    let result = 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '1') {
                result++;
                visitIsland(i, j);
            }
        }
    }

    return result;

    function visitIsland(i: number, j: number) {
        grid[i][j] = '0';

        const directions = [
            [-1, 0],
            [0, 1],
            [1, 0],
            [0, -1],
        ];
        for (const direction of directions) {
            const i2 = i + direction[0];
            const j2 = j + direction[1];
            if (
                i2 >= 0 &&
                i2 < m &&
                j2 >= 0 &&
                j2 < n &&
                grid[i2][j2] === '1'
            ) {
                visitIsland(i2, j2);
            }
        }
    }
}
